package com.tgy.heap;

import com.tgy.util.printer.BinaryTreeInfo;


import java.util.Comparator;
import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-11-26 15:09
 */
public class BinaryHeap_01<E> implements Heap<E>, BinaryTreeInfo {

    private int size;

    private E[] container;

    private Comparator<E> comparator;

    private final static int INIT_CAPACITY = 10;

    private int capacity;

    public BinaryHeap_01() {

        this(INIT_CAPACITY,null);
    }

    public BinaryHeap_01(int capacity) {

        this(capacity,null);
    }

    public BinaryHeap_01(Comparator<E> comparator) {
        this(INIT_CAPACITY,comparator);
    }

    public BinaryHeap_01(int capacity, Comparator<E> comparator) {

        if (capacity < INIT_CAPACITY) {

            capacity = INIT_CAPACITY;
        }

        this.comparator = comparator;
        this.capacity = capacity;
        this.container = (E[])new Object[capacity];
    }

    public BinaryHeap_01(E[] container,Comparator<E> comparator) {

        this.container = (E[]) new Object[container.length];
        this.size = this.capacity = this.container.length;
        this.comparator = comparator;

        for (int i = 0; i < container.length; i++) {

            this.container[i] = container[i];
        }

        heapify();
    }

    @Override
    public int size() {

        return size;
    }

    @Override
    public boolean isEmpty() {

        return size == 0;
    }

    @Override
    public void clear() {

        for (int i = 0; i < size; i++) {

            container[i] = null;
        }

        size = 0;
    }

    @Override
    public void add(E element) {

        checkElement(element);

        ensureContainer();

        container[size] = element;
        siftUp(size++);
    }

    @Override
    public E get() {

        if (size == 0){
            return null;
        }

        return container[0];
    }

    @Override
    public E remove() {

        if (size == 0) {

            return null;
        }

        E e = container[0];
        container[0] = container[--size];
        siftDown(0);
        return e;
    }

    @Override
    public E replace(E element) {

        checkElement(element);

        if (size == 0) {

            return null;
        }
        E e = container[0];
        container[0] = element;
        siftDown(0);
        return e;
    }

    @Override
    public void tranversal(Visitor<E> visitor) {

        for (int i = 0; i < size; i++) {

            if (visitor.visit(container[i])) {

                return;
            }
        }

    }

    @Override
    public Object root() {

        if (isEmpty()) {

            return null;
        }
        return 0;
    }

    @Override
    public Object left(Object node) {

        Integer root = (Integer) node;

        int index = (root << 1) + 1;
        return index < size ? index: null;
    }

    @Override
    public Object right(Object node) {

        Integer root = (Integer) node;

        int index = (root << 1) + 2;
        return index < size ? index: null;
    }

    @Override
    public Object string(Object node) {

        Integer root = (Integer) node;

        return container[root];
    }

    private void siftUp(int index) {

        /**
         *          0
         *         1  2
         *        3  4
         */

        int parent = (index - 1) >> 1;

        E tmp = container[index];

        while (parent >= 0) {

            if (cmp(tmp, container[parent]) > 0) {

                container[index] = container[parent];
            }else {

                break;
            }

            index = parent;
            parent = (index - 1) >> 1;
        }

        container[index] = tmp;
    }

    /**
     * 下滤
     * @param index
     */
    private void siftDown(int index) {


        /**
         *          0
         *         1   2
         *        3 4 5 6
         */

        E tmp = container[index];

        while (true) {

            int maxIndex = (index << 1) + 1;

            if (maxIndex >= size) {
                break;
            }

            int right = maxIndex + 1;

            if (right < size && cmp(maxIndex,right) < 0) {

                maxIndex = right;
            }

            if (cmp(tmp, container[maxIndex]) >= 0) {

                break;
            }

            container[index] = container[maxIndex];

            index = maxIndex;
        }

        container[index] = tmp;

    }

    private void ensureContainer() {

        if (size < capacity) {

            return;
        }

        capacity = capacity + (capacity >> 1);

        E[] newContainer = (E[]) new Object[capacity];

        for (int i = 0; i < size; i++) {

            newContainer[i] = container[i];
        }

        container = newContainer;
    }

    private int cmp(E e1, E e2) {

        if (comparator != null) {

            return comparator.compare(e1,e2);
        }

        return ((Comparable<E>)e1).compareTo(e2);
    }

    private int cmp(int i1, int i2) {

        return cmp(container[i1],container[i2]);
    }

    private void checkElement(E e) {

        if (Objects.isNull(e)) {

            throw new IllegalArgumentException("element not null");
        }
    }

    private void swap(int i1, int i2) {

        E tmpE = container[i1];
        container[i1] = container[i2];
        container[i2] = tmpE;
    }

    private void heapify() {

        /**
         * 自上而下的上滤是相等于一个元素一个元素的添加 时间复杂的为 n*logn
         *
         * 自下而上的下滤 就是先把小块变成最大最小堆，最后把整个变成堆
         */
        /**
         *          0
         *         1   2
         *        3 4 5 7
         */

        if (size <= 1) {
            return;
        }

        for (int i = size >> 1; i >= 0; i--) {

            siftDown(i);
        }

    }

}
